package com.cat.enumerate;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/count-number-of-maximum-bitwise-or-subsets/?envType=problem-list-v2&envId=enumeration
 * @create 2025/9/21 16:56
 * @since JDK17
 */

public class Solution10 {
    int ans, max;
    void dfs(int[] nums, int i, int cur) {
        if (i == nums.length) {
            ans += max == cur ? 1 : 0;
            return;
        }
        dfs(nums, i + 1, cur | nums[i]);
        dfs(nums, i + 1, cur);
    }

    public int countMaxOrSubsets(int[] nums) {
        for (int num : nums) {
            max |= num;
        }
        dfs(nums, 0, 0);
        return ans;
    }
}
